An Effective Chromosome Representation for Evolving Flexible Job Shop Schedules

Joc Cing Tay and Djoko Wibowo

Abstract. As the Flexible Job Shop Scheduling Problem (or FJSP) is strongly NP-hard, using an evolutionary approach to find near-optimal solutions requires effective chromosome representations as well as carefully designed parameters for crossover and mutation to achieve efficient search. This paper proposes a new chromosome representation and a design of related parameters to solve the FJSP efficiently. The results of applying the new chromosome representation for solving the 10 jobs x 10 machines FJSP are compared with three other chromosome representations. Empirical experiments show that the proposed chromosome representation obtains better results than the others in both quality and processing time required.

Keywords. Flexible Job Shop Scheduling Problem, Genetic Algorithm, Chromosome Representation

LNCS 3103, p. 210 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004